package _05_二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 */
public class _102_二叉树的层序遍历 {

    // 迭代
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> list = new ArrayList<>();
        if (root == null) return list;

        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);
        int levelSize = 1;
        ArrayList<Integer> containers = new ArrayList<>();
        while (!nodes.isEmpty()) {

            TreeNode node = nodes.poll();
            containers.add(node.val);

            if (node.left != null) {
                nodes.offer(node.left);
            }

            if (node.right != null) {
                nodes.offer(node.right);
            }

            if (--levelSize == 0) {
                // 当前层已经遍历完
                levelSize = nodes.size();
                list.add(containers);
                containers = new ArrayList<>();
            }

        }

        return list;
    }
}
